/**
 * 
 */
package tree.passed2;

/**
 * @author xyyi
 *
 */
public class BalancedBinaryTree {
	/**
	 * Definition for binary tree
	 */

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	Given a binary tree, determine if it is height-balanced.

	For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
	 */
	public boolean isBalanced(TreeNode root) {
		return isBalancedHelper(root) < 0 ? false : true;
	}

	public int isBalancedHelper(TreeNode root) {
		if (root == null)
			return 0;

		int left = isBalancedHelper(root.left);
		int right = isBalancedHelper(root.right);

		if (left < 0 || right < 0 || Math.abs(left - right) > 1)
			return -1;

		return Math.max(left, right) + 1;
	}

	/**
	 * 
	 */
	public BalancedBinaryTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
